package list;

public class ListCycle {

	//检测环的入口结点
	public ListNode detectCycle(ListNode head) {
        //如果有环，则两者一定是在环中相遇
        ListNode meetNode = meetNode(head);
		if(meetNode == null){
			return null;
		}
        ListNode slow = head;
        //当两者再次相遇时，即为链表中环的入口
        while(slow != meetNode){
            slow = slow.next;
            meetNode = meetNode.next;
        }
        return slow;
    }
    public ListNode meetNode(ListNode head){
        if(head == null){
            return null;
        }
        ListNode meetNode;
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                meetNode = slow;
                return meetNode;
            }
        }
        //注意循环的条件是fast不为空，并且fast.next不为空
        //若只有一个头结点，并且头结点的next指向头结点，仍然应该返回true
        return head.next == head ? head : null;
    }
    public boolean hasCycle(ListNode head){
        if(head == null){
            return false;
        }
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        //注意循环的条件是fast不为空，并且fast.next不为空
        //若只有一个头结点，并且头结点的next指向头结点，仍然应该返回true
        return head.next == head;
    }
}
